import java.util.ArrayList;
import java.util.HashMap;

public class FollowSet {
    /**
     * 计算 Follow 集合
     * 
     * @param formulas     产生式列表
     * @param terminals    终结符列表
     * @param nonTerminals 非终结符列表
     * @param firsts       每个非终结符的 First 集合
     * @param follows      每个非终结符的 Follow 集合
     */

    public void setFollow(ArrayList<Formula> formulas, ArrayList<String> terminals,
            ArrayList<String> nonTerminals, HashMap<String, ArrayList<String>> firsts,
            HashMap<String, ArrayList<String>> follows) {
        // 初始化每个非终结符的 Follow 集合
        for (String nonTerminal : nonTerminals) {
            follows.put(nonTerminal, new ArrayList<String>());
        }

        // 将 # 加入到 Follow(S) 中，S 为起始符号
        follows.get(Config.initSymbol).add("#");

        boolean flag;
        while (true) {
            flag = true; // 标志位，表示 Follow 集合是否发生变化
            for (Formula formula : formulas) {
                String left = formula.getLeft();
                String[] right = formula.getRight();

                // 遍历产生式右边的符号串
                for (int i = 0; i < right.length; i++) {
                    String symbol = right[i];

                    if (nonTerminals.contains(symbol)) { // 如果右边的符号是非终结符
                        // 尝试将右边后续符号的 First 集合添加到当前非终结符的 Follow 集合中
                        boolean canBeNull = true; // 记录是否可以推导为空串
                        for (int j = i + 1; j < right.length; j++) {
                            String nextSymbol = right[j];

                            // 获取 nextSymbol 的 First 集合，并加入到当前非终结符的 Follow 集合中
                            for (String firstSymbol : firsts.get(nextSymbol)) {
                                if (!follows.get(symbol).contains(firstSymbol) && (!firstSymbol.equals("$"))) {
                                    follows.get(symbol).add(firstSymbol);
                                    flag = false; // Follow 集合发生了变化
                                }
                            }

                            // 如果 nextSymbol 不能推导出空串，则停止
                            if (!firsts.get(nextSymbol).contains("$")) {
                                canBeNull = false;
                                break;
                            }
                        }

                        // 如果后续符号可以推导出空串，将 Follow(A) 加入到 Follow(B) 中
                        if (canBeNull) {
                            for (String followLeft : follows.get(left)) {
                                if (!follows.get(symbol).contains(followLeft)) {
                                    follows.get(symbol).add(followLeft);
                                    flag = false; // Follow 集合发生了变化
                                }
                            }
                        }
                    }
                }
            }

            // 如果 Follow 集合没有发生变化，则结束计算
            if (flag) {
                break;
            }
        }

        // 清除 Follow 集合中的 #
        for (String nonTerminal : nonTerminals) {
            ArrayList<String> followSet = follows.get(nonTerminal);
            followSet.remove("#"); // 移除 # 符号
        }

        // 为 Follow 集合加上 #
        for (String nonTerminal : nonTerminals) {
            follows.get(nonTerminal).add("#");
        }

    }

    // 判断是否产生$，也就是没了
    public boolean isCanBeNull(ArrayList<Formula> formulas, String symbol) {
        String[] rights;
        // 遍历每个文法
        for (Formula formula : formulas) {
            // 寻找产生式
            if (formula.getLeft().equals(symbol)) {
                // symbol->[rights]
                rights = formula.getRight();
                if (rights[0].equals("$")) {
                    // e.g:symbol->$
                    return true;
                }
            }
        }
        return false;
    }
}